package leetcode.题库.链表;

/**
 * 合并 K 个升序链表
 *
 * @author yanzhenming
 * @date 2023/3/23  17:40
 */

/**
 * 描述
 *
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */

import leetcode.题库.pubclass.ListNode;

/**
 * 思路
 *
 * 合并两个链表+递归
 */
public class Solution23 {

    public ListNode mergeKLists(ListNode[] lists) {
        return mergeKLists(lists, 0, lists.length - 1);
    }
    public ListNode mergeKLists(ListNode[] lists, int lp, int rp) {
        if (lp == rp) return lists[lp];
        if (lp > rp) return null; // // 防止右侧越界
        int mid = (lp + rp) >> 1;
        return mergeTwoLists(mergeKLists(lists, lp, mid), mergeKLists(lists, mid+1, rp));
    }
    public ListNode mergeTwoLists(ListNode listNode1, ListNode listNode2) {
        ListNode head = new ListNode();
        ListNode temp = head;
        while (listNode1 != null && listNode2 != null) {
            if (listNode1.val < listNode2.val) {
                temp.next = listNode1;
                temp = temp.next;
                listNode1 = listNode1.next;
            } else {
                temp.next = listNode2;
                temp = temp.next;
                listNode2 = listNode2.next;
            }
        }
        if (listNode1 != null) temp.next = listNode1;
        if (listNode2 != null) temp.next = listNode2;
        return head.next;
    }
}
